package DataStructrue.string;

import java.util.ArrayList;
import java.util.List;
//字符串
public class Strings {

    //字符串哈希值
    public static int hash(String s,int l,int r){
        int n=s.length();
        int[][] pre=new int[n+1][2];//前缀哈希值,双重hash
        long base=131;//取一个质数作基数
        int[] mod={19260817,19660813};//分别对两个大质数取模
        for (int i = 1; i <=n ; i++) {
            for (int j = 0; j < 2; j++) {
                pre[i][j] =  (int)((pre[i - 1][j] * base + s.charAt(i - 1) - 'a' + 1)%mod[j]);
            }
        }
        return pre[r][0]-pre[l-1][0]*(int)Math.pow(131,r-l+1);//返回某个区间的哈希值
    }

    //kmp单字符串匹配
    public static int kmp(String text,String pattern){
        int n=text.length(),m=pattern.length();
        int[] next=new int[m];//pattern[0,i-1]的最长相等真前后缀长度
        next[0] = -1;//没有相等时便于计算下一个
        //对于后面的长度,最多比前一个长度+1
        for(int i = 1;i < m;i++){
            int k = next[i-1];//pattern[0,i-2]中,pattern[0,k-1]和pattern[i-1-k,i-2]是相等的
            //若k与i-1位置不同,那么长度要缩短,就要在pattern[0,k-1]中寻找最长的真前缀可以和pattern[i-1-k,i-2]中某个真后缀匹配
            //由于pattern[0,k-1]和pattern[i-1-k,i-2]相等,那么k可以前移至next[k],此时pattern[0,next[k]-1]和pattern[i-1-next[k],i-2]也相等
            //只需比较next[k]与i-1位置,如果相同,长度为next[k]+1,否则继续前移
            while (k >= 0 && pattern.charAt(k) != pattern.charAt(i-1)){
                k = next[k];
            }
            next[i] = k + 1;//若k与i-1位置也相等,那么长度+1.遇到k=0时跳出变为-1,当前长度为0
        }
        int i,j;
        for (i = 0,j=0; i < n&&j<m;) {
            if(j==-1||text.charAt(i)==pattern.charAt(j)){
                i++;j++;//当前字符匹配.没有相等真前后缀时pattern后移一位从头开始匹配
            }else
                j=next[j];
            //当前字符不匹配,j前移,pattern由idx后移至i-next[j]位置,因为在[idx+1,i-next[j]-1]位置上
            //i之前对应的pattern前缀一定和text不匹配,如果匹配则说明这一段前缀与text[idx,i]的某个后缀相等
            //而next记录的是最长相等真前后缀,两者矛盾
        }
        if(j==m)//匹配成功
            return i-m;
        return -1;//匹配失败
    }

    //字符串后缀排序后的索引[1,n]
    public static int[] suffixArr(String s) {
        int n = s.length();
        int[][] sort = new int[n][3];
        //第一关键字
        for (int i = 0; i < n; i++) {
            sort[i][0] = s.charAt(i) - '0' + 1;
        }
        for (int k = 1; k < n; k <<= 1) {
            //第二关键字
            for (int i = 0; i < n; i++) {
                sort[i][1] = i + k < n ? sort[i + k][0] : 0;
                sort[i][2] = i;
            }
            //根据第二关键字和第一关键字排序
            for (int i = 1; i >= 0; i--) {
                List<int[]>[] bucket = new ArrayList[n + 1];
                for (int j = 0; j < n; j++) {
                    int num = sort[j][i];
                    if (bucket[num] == null)
                        bucket[num] = new ArrayList<>();
                    bucket[num].add(sort[j]);
                }
                //放回
                for (int j = 0, next = 0; j < n + 1; j++) {
                    if (bucket[j] == null) continue;
                    for (int l = 0; l < bucket[j].size(); l++) {
                        sort[next++] = bucket[j].get(l);
                    }
                }
            }
            //新的排序结果
            int[] nsort = new int[n];
            int rank = 0;
            for (int i = 0; i < n; i++) {
                if (i == 0)
                    nsort[sort[i][2]] = ++rank;
                else if (sort[i][0] == sort[i - 1][0] && sort[i][1] == sort[i - 1][1])
                    nsort[sort[i][2]] = rank;
                else
                    nsort[sort[i][2]] = ++rank;
            }
            if (k << 1 >= n)
                return nsort;
            //作为下一轮的第一关键字
            for (int i = 0; i < n; i++) {
                sort[i][0] = nsort[i];
            }
        }
        return null;
    }

    //寻找回文串
    public static List<int[]> manacher(String s){
        int n=s.length()*2+1;
        char[] cs=new char[n];
        for (int i = 0; i < n; i++) {
            cs[i]=i%2==0?'*':s.charAt((i-1)/2);
        }
        int[] d=new int[n];//以原字符串每个位置为中心的最大回文长度,以修改后字符串每个位置为中心的最大回文半径(不计中心)
        int c=0,r=0;//右边界最大的子串中心和右边界
        for (int i = 0; i < n; i++) {
            int j=2*c-i;//i的关于c的对称位置
            //如果i在r左边,那么在c的回文范围内i附近的回文情况与j相同,此时需要判断j的回文范围是否超出c的回文范围,取较小值
            if(r>i) d[i]=Math.min(r-i,d[j]);
            else d[i]=0;
            //确定i的至少回文长度后向两边扩展继续判断
            while(i-d[i]-1>=0&&i+d[i]+1<n&&cs[i+d[i]+1]==cs[i-d[i]-1])
                d[i]++;
            //更新c,r
            if(d[i]+i>r){
                r=d[i]+i;
                c=i;
            }
        }
        List<int[]> ans=new ArrayList<>();//以某位置为中心长度至少为2的最长回文串
        for (int i = 0; i < n; i++) {
            if(d[i]<2) continue;
            ans.add(new int[]{(i-d[i])/2,(i+d[i]-2)/2});
        }
        return ans;
    }


}
